1. Field of the Invention
The present invention relates to scheduling systems, such as a factory scheduling system for an organization, which are used to assign resources with limited capacity to activities over time under several constraints such as prefixed partial ordering, while achieving the organization's objectives as much as possible.
2. Description of the Prior Art
So-called scheduling systems have been developed and used over the last several decades by the researchers and practitioners in the field of Operations Research (OR) and Artificial Intelligence (AI). In the beginning, researchers in OR developed several mathematical methods, such as Linear Programming, Integer Programming and Dynamic Programming, and tried to solve the scheduling problem by using those methods. Buts as the scheduling problem is proven to be a NP-hard problem, those mathematical methods failed to solve a large scheduling problem in a reasonable amount of time. To avoid the computationally expensive calculations inherent in these older OR techniques, heuristic simulation methods using sophisticated dispatching rules were developed and used to solve large scheduling problems. These methods have achieved great success in solving scheduling problems efficiently, and therefore they are still widely used all over the world. The details of those techniques developed in OR are described fully in many textbooks, such as "SEQUENCING AND SCHEDULING: An introduction to the Mathematic of the Job-Shop" by Simon French, Ellis Horwood, 1982.
The difficulty of scheduling problems is not solely caused by the size of the problem. The complexity of the constraints to be satisfied in the schedule can easily make scheduling intractable. For example, there may be precedence constraints connecting activities which specify which activities must precede which other activities, and by how much of a delay, or by how much allowed overlap. Or two particular activities may interfere with each other and be unable to use the same required resource simultaneously. Or it may not be possible to use two resources simultaneously during certain parts of the day or on the same activity. Or a resource may be unavailable during specified intervals due to planned maintenance or planned use outside the system. The above mathematical methods may be able to model those constraints precisely, but they can not find a solution in a timely way. And, the above heuristic dispatching methods don't have sufficient flexibility to model such complicated constraints. To overcome the difficulty, several scheduling systems have been developed by researches in AI, such as ISIS taught by Mark Fox. ISIS is the first scheduling systems that can model variety of constraints and find a schedule which satisfies those constraints in moderate time. After the success of ISIS, there appeared several scheduling systems which utilize rich representation capability of knowledge representation languages and efficient heuristic search techniques, which have been developed in the research of AI. These techniques are well known; see the description by Mark Fox in "Constraint-Directed Search: A Case Study of Job-Shop Scheduling", Pitman, London, 1987. The well known information about OR or AI techniques used in the scheduling problem is not repeated herein except as needed for one of ordinary skill in this art to understand the present invention.
The remaining difficulty of scheduling problems that is left unsolved until today is ambiguity and uncertainty involved in the scheduling problem. First, user's scheduling preferences are typically context dependent (e.g., may depend on the state of the scheduling environment at a particular time). Second interactions among preferences and effective tradeoffs often depend on the particular schedule produced. This means that generally a user cannot fully specify his/her preferences in advance and in the absence of particular scheduling results. Consider, for example, the situation where a user prefers using machine-b over a lower quality substitutable machine-a for processing order-x. This preference may be due to the desire to obtain high quality results for order-x since it belongs to a very important client. If, however, the schedule indicates that order-x is tardy by an amount above an acceptable tardiness threshold due to demands on machine-b (by orders more important than order-x), then, the user may decide to use the less preferable machine for order-x. On the other hand, if the tardiness was below the threshold, he/she may prefer to allow order-x to be tardy in exchange for producing a higher quality product. Nevertheless, to use the scheduling system developed so far, a user of the system is required to express his/her objectives of the schedule in a simple and clear way, which is usually very difficult for the user because of the above reasons. Third, factories are dynamic environments. Unexpected events, such as operator absence, power failure and machine breakdowns frequently happen. Therefore, it is necessary for the scheduling system to flexibly modify the schedule to take into account the changed planning context, which may have also caused changes in desired scheduling tradeoffs and preferences. Although initial progress has been made in schedule repair based on a static reactive model, there is the need for more flexible approaches. (See the detailed description in an article by Peng S. Ow et al. in "Reactive plan revision", Proceedings of Seventh American Association of Artificial Intelligence. pp 77-82, 1988.)